//
// Created by xili on 2024/9/22 18:31.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

//记忆化搜索
class Solution1 {
public:
    bool wordBreak(string s, vector <string> &wordDict) {
        int n = s.size();
        unordered_set <string> st = {wordDict.begin(), wordDict.end()};
        vector<int> memo(n, -1);
        auto dfs = [&](auto &&dfs, int i) -> bool {
            if (i < 0) return true;
            if (memo[i] != -1) return memo[i];
            //枚举每一个切分点，不能为空
            bool ok = false;
            for (int k = i; k >= 0; k--) {
                string suffix = s.substr(k, i - k + 1);
                ok = ok || (st.contains(suffix) && dfs(dfs, k - 1));
                if (ok) return memo[i] = true;
            }
            return memo[i] = false;
        };
        return dfs(dfs, n - 1);
    }
};


//严格位置依赖
class Solution2 {
public:
    bool wordBreak(string s, vector <string> &wordDict) {
        int n = s.size();
        unordered_set <string> st = {wordDict.begin(), wordDict.end()};
        vector<bool> f(n + 1, false);
        f[0] = true;
        for (int i = 0; i < n; i++) {
            //枚举切分点
            bool ok = false;
            for (int k = i; k >= 0; k--) {
                string suffix = s.substr(k, i - k + 1);
                ok = ok || (st.contains(suffix) && f[k]);
                if (ok) {
                    f[i + 1] = true;
                    break;
                }
            }
        }
        return f[n];
    }
};